{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Build an Array With Stack Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: buildArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #用栈操作构建数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>target</code> 和一个整数 <code>n</code>。每次迭代，需要从&nbsp; <code>list = { 1 , 2 , 3 ..., n }</code> 中依次读取一个数字。</p>\n",
    "\n",
    "<p>请使用下述操作来构建目标数组 <code>target</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>\"Push\"</code>：从 <code>list</code> 中读取一个新元素， 并将其推入数组中。</li>\n",
    "\t<li><code>\"Pop\"</code>：删除数组中的最后一个元素。</li>\n",
    "\t<li>如果目标数组构建完成，就停止读取更多元素。</li>\n",
    "</ul>\n",
    "\n",
    "<p>题目数据保证目标数组严格递增，并且只包含 <code>1</code> 到 <code>n</code> 之间的数字。</p>\n",
    "\n",
    "<p>请返回构建目标数组所用的操作序列。如果存在多个可行方案，返回任一即可。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = [1,3], n = 3\n",
    "<strong>输出：</strong>[\"Push\",\"Push\",\"Pop\",\"Push\"]\n",
    "<strong>解释： \n",
    "</strong>读取 1 并自动推入数组 -&gt; [1]\n",
    "读取 2 并自动推入数组，然后删除它 -&gt; [1]\n",
    "读取 3 并自动推入数组 -&gt; [1,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = [1,2,3], n = 3\n",
    "<strong>输出：</strong>[\"Push\",\"Push\",\"Push\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>target = [1,2], n = 4\n",
    "<strong>输出：</strong>[\"Push\",\"Push\"]\n",
    "<strong>解释：</strong>只需要读取前 2 个数字就可以停止。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= target[i] &lt;= n</code></li>\n",
    "\t<li><code>target</code> 严格递增</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [build-an-array-with-stack-operations](https://leetcode.cn/problems/build-an-array-with-stack-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [build-an-array-with-stack-operations](https://leetcode.cn/problems/build-an-array-with-stack-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3]\\n3', '[1,2,3]\\n3', '[1,2]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        target = [0] + target\n",
    "        ans = []\n",
    "        for i in range(1, len(target)):\n",
    "            if target[i] - target[i-1] == 1:\n",
    "                ans.append(\"Push\")\n",
    "            else:\n",
    "                for _ in range(target[i] - target[i-1] - 1):\n",
    "                    ans.append(\"Push\")\n",
    "                    ans.append(\"Pop\")\n",
    "                ans.append(\"Push\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        i, n = 0, len(target)\n",
    "        target = target + [0]\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            for _ in range(target[i] - target[i-1] - 1):\n",
    "                ans.extend([\"Push\", \"Pop\"])\n",
    "            ans.append(\"Push\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans = []\n",
    "        m, i, j = len(target), 1, 0\n",
    "        while i <= n and j < m:\n",
    "            ans.append(\"Push\")\n",
    "            if target[j] != i:\n",
    "                ans.append(\"Pop\")\n",
    "            else:\n",
    "                j += 1\n",
    "            i += 1\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        lists = [i for i in range(1,n+1)]\n",
    "\n",
    "        index = 0\n",
    "        for num in target:\n",
    "            while num != lists[index]:\n",
    "                res.append('Push')\n",
    "                res.append('Pop')\n",
    "                index += 1\n",
    "            res.append('Push')\n",
    "            index += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: list[int], n: int) -> list[str]:\n",
    "        p=1\n",
    "        ans=[]\n",
    "        for i in range(len(target)):\n",
    "            while  target[i]!=p:\n",
    "                p+=1\n",
    "                ans.append('Push')\n",
    "                ans.append('Pop')\n",
    "            ans.append('Push')\n",
    "            p+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        idx = 0\n",
    "        ans = []\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            if idx >= len(target):\n",
    "                break\n",
    "            if i == target[idx]:\n",
    "                ans.append('Push')\n",
    "                idx += 1\n",
    "            elif i < target[idx]:\n",
    "                ans.append('Push')\n",
    "                ans.append('Pop')\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        m = len(target)\n",
    "        ptr = 0\n",
    "        ans = []\n",
    "        for i in range(1, n + 1):\n",
    "            if ptr < m:\n",
    "                if i == target[ptr]:\n",
    "                    ans.append(\"Push\")\n",
    "                    ptr += 1\n",
    "                else:\n",
    "                    ans.append(\"Push\")\n",
    "                    ans.append(\"Pop\")\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans = []\n",
    "        index = 0\n",
    "        num = 1\n",
    "        while index < len(target):\n",
    "            if target[index] == num:\n",
    "                ans.append('Push')\n",
    "                index += 1\n",
    "                num += 1\n",
    "            else:\n",
    "                ans.append('Push')\n",
    "                ans.append('Pop')\n",
    "                num += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        isintarget=[0]*n\n",
    "        res=[]\n",
    "        tmo=target[-1]\n",
    "        for t in target:\n",
    "            isintarget[t-1]=1\n",
    "        for i in range(tmo):\n",
    "            if isintarget[i]==1:\n",
    "                res.append(\"Push\")\n",
    "            elif isintarget[i]==0:\n",
    "                res.append(\"Push\")\n",
    "                res.append(\"Pop\")\n",
    "        return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        return list(chain(*([\"Push\",\"Pop\"]*(b-a-1)+[\"Push\"] for a,b in zip([0]+target, target))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans = []\n",
    "        cur = 1\n",
    "        for v in target:\n",
    "            while cur < v:\n",
    "                ans+=[\"Push\",\"Pop\"]\n",
    "                cur+=1\n",
    "            ans.append(\"Push\")\n",
    "            cur+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        i=0\n",
    "        j=1\n",
    "        while j <= n:\n",
    "            if i<len(target) and j == target[i]:\n",
    "                res.append('Push')\n",
    "                i+=1\n",
    "            elif i<len(target) and j != target[i]:\n",
    "                res.append('Push')\n",
    "                res.append('Pop')\n",
    "            j+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res=[]\n",
    "        for i in range(1,target[-1]+1):\n",
    "            if i in target:\n",
    "                res.append('Push')\n",
    "            else:\n",
    "                res.append('Push')\n",
    "                res.append('Pop')\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        idx = 0\n",
    "        for v in range(1, n+1):\n",
    "            res.append('Push')\n",
    "            if v == target[-1]:\n",
    "                break\n",
    "            if v == target[idx]:\n",
    "                idx += 1\n",
    "            else:\n",
    "                res.append('Pop')\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        i=0\n",
    "        j=1\n",
    "        while j <= n:\n",
    "            if i<len(target) and j == target[i]:\n",
    "                res.append('Push')\n",
    "                i+=1\n",
    "            elif i<len(target) and j != target[i]:\n",
    "                res.append('Push')\n",
    "                res.append('Pop')\n",
    "            j+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        cur = 1\n",
    "        ans = []\n",
    "        for num in target:\n",
    "            n = num - cur\n",
    "            ans.extend([\"Push\", \"Pop\"] * n)\n",
    "            ans.append(\"Push\")\n",
    "            cur = num + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res=[]\n",
    "        i=0\n",
    "        l=len(target)\n",
    "        base=1\n",
    "        while i<l:\n",
    "            if target[i]!=base:\n",
    "                while target[i]-base>0:\n",
    "                    res.append('Push')\n",
    "                    res.append('Pop')\n",
    "                    base+=1\n",
    "            res.append('Push')\n",
    "            base+=1\n",
    "            i+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "\n",
    "        i = 1\n",
    "        for num in target:\n",
    "            while num > i:\n",
    "                res.append(\"Push\")\n",
    "                res.append(\"Pop\")\n",
    "                i += 1\n",
    "            if num == i:\n",
    "                res.append(\"Push\")\n",
    "                i += 1\n",
    "                        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        i = 1\n",
    "        ans = []\n",
    "        while i <= target[-1]:\n",
    "            while not i in target:\n",
    "                ans.append(\"Push\")\n",
    "                ans.append(\"Pop\")\n",
    "                i += 1\n",
    "            ans.append(\"Push\")\n",
    "            i += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        return list(chain.from_iterable([\"Push\",\"Pop\"]*(b-a-1)+[\"Push\"] for a,b in zip([0]+target, target)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        t = 0\n",
    "        for i in range(1,n+1):\n",
    "            if t==len(target):\n",
    "                break\n",
    "            if i < target[t]:\n",
    "                res.append(\"Push\")\n",
    "                res.append(\"Pop\")\n",
    "            else:\n",
    "                res.append(\"Push\")\n",
    "                t+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.strPush = \"Push\"\n",
    "        self.strPop = \"Pop\"\n",
    "\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        retVal = []\n",
    "\n",
    "        targetSize = len(target)\n",
    "        targetIndex = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if targetIndex >= targetSize:\n",
    "                break\n",
    "\n",
    "            if i == target[targetIndex]:\n",
    "                retVal.append(self.strPush)\n",
    "                targetIndex += 1\n",
    "            else:\n",
    "                retVal.append(self.strPush)\n",
    "                retVal.append(self.strPop)\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res=[]\n",
    "        tmp=1\n",
    "        for i in target:\n",
    "            for j in range(tmp,i):\n",
    "                res.append('Push')\n",
    "                res.append('Pop')\n",
    "            res.append('Push')\n",
    "            tmp=i+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans = []\n",
    "        idx = 1\n",
    "        for ele in target:\n",
    "            for i in range(idx, n + 1):\n",
    "                if i == ele:\n",
    "                    ans.append(\"Push\")\n",
    "                elif i < ele:\n",
    "                    ans.append(\"Push\")\n",
    "                    ans.append(\"Pop\")\n",
    "                else:\n",
    "                    break\n",
    "            idx = i\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        idx = 0\n",
    "        target_len = len(target)\n",
    "        ans = []\n",
    "        for i in range(1, n + 1):\n",
    "            if idx == target_len:\n",
    "                break\n",
    "            if target[idx] == i:\n",
    "                ans.append('Push')\n",
    "                idx += 1\n",
    "            else:\n",
    "                ans.extend(['Push', 'Pop'])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans = []\n",
    "        target_idx = 0\n",
    "        for num in range(1, n + 1):\n",
    "            if target_idx >= len(target):\n",
    "                break\n",
    "            if num == target[target_idx]:\n",
    "                ans += [\"Push\"]\n",
    "                target_idx += 1\n",
    "            else:\n",
    "                ans += [\"Push\", \"Pop\"]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\r\n",
    "        ans = []\r\n",
    "        idx = 0\r\n",
    "        for i in range(1, n+1):\r\n",
    "            if idx == len(target):\r\n",
    "                break\r\n",
    "            if i == target[idx]:\r\n",
    "                ans.append(\"Push\")\r\n",
    "                idx += 1\r\n",
    "            else:\r\n",
    "                ans.append(\"Push\")\r\n",
    "                ans.append(\"Pop\")\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        l1 = []\n",
    "        p = 1\n",
    "        for i in range (len(target)):\n",
    "            if target[i] == p:\n",
    "                l1.append(\"Push\")\n",
    "                p += 1\n",
    "            else:\n",
    "                while target[i] != p:\n",
    "                    l1.append(\"Push\")\n",
    "                    l1.append(\"Pop\")\n",
    "                    p += 1\n",
    "                l1.append(\"Push\")\n",
    "                p += 1\n",
    "        return l1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans = []\n",
    "        m, i, j = len(target), 1, 0\n",
    "        while i <= n and j < m:\n",
    "            ans.append(\"Push\")\n",
    "            if target[j] != i:\n",
    "                ans.append(\"Pop\")\n",
    "            else:\n",
    "                j += 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        cur = 0\n",
    "        l = len(target)\n",
    "        for i in range(1,target[-1]+1):\n",
    "            res.append('Push')\n",
    "            if i != target[cur]:\n",
    "                res.append('Pop')\n",
    "            else:\n",
    "                cur += 1\n",
    "                if cur == l:\n",
    "                    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans=[]\n",
    "        i=0\n",
    "        while 1:\n",
    "            i+=1\n",
    "            ans.append('Push')\n",
    "            if i not in target:\n",
    "                ans.append('Pop')\n",
    "            elif i==target[-1]:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        i = 1\n",
    "        for x in target:\n",
    "            while i != x:\n",
    "                res.append(\"Push\")\n",
    "                res.append(\"Pop\")\n",
    "                i += 1\n",
    "                if i == n + 1:\n",
    "                    i = 1\n",
    "            res.append(\"Push\")\n",
    "            i += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        i = 1\n",
    "        j = 0\n",
    "        ans = []\n",
    "        while i <= target[-1]:\n",
    "            if i == target[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "                ans.append('Push')\n",
    "            else:\n",
    "                i += 1\n",
    "                ans.append('Push')\n",
    "                ans.append('Pop')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        i=0\n",
    "        j=1\n",
    "        while j <= n:\n",
    "            if i<len(target) and j == target[i]:\n",
    "                res.append('Push')\n",
    "                i+=1\n",
    "            elif i<len(target) and j != target[i]:\n",
    "                res.extend(['Push','Pop'])\n",
    "            j+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans, diff = [], 0\n",
    "        for i, v in enumerate(target, 1):\n",
    "            if i + diff == v:\n",
    "                ans.append(\"Push\")\n",
    "            else:\n",
    "                ans += [\"Push\", \"Pop\"] * (v - i - diff)\n",
    "                ans.append(\"Push\")\n",
    "                diff = v - i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        idx = 0\n",
    "        for i in range(1, n+1):\n",
    "            if idx >= len(target):\n",
    "                break\n",
    "            if i == target[idx]:\n",
    "                res.append('Push')\n",
    "                idx += 1\n",
    "            else:\n",
    "                res.append('Push')\n",
    "                res.append('Pop')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        operations = []\n",
    "        target_index = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if target_index >= len(target):\n",
    "                break\n",
    "\n",
    "            operations.append(\"Push\")\n",
    "            if target[target_index] == i:\n",
    "                target_index += 1\n",
    "            else:\n",
    "                operations.append(\"Pop\")\n",
    "\n",
    "        return operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans = []  \n",
    "        j = 0    \n",
    "        for i in range(1, n + 1):  \n",
    "            if j >= len(target):\n",
    "                break  \n",
    "            ans.append(\"Push\")  \n",
    "            if target[j] == i:\n",
    "                j += 1  \n",
    "            else:\n",
    "                ans.append(\"Pop\") \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans = []\n",
    "        for x in range(1,n+1):\n",
    "            if target and x == target[0]:\n",
    "                ans.append(\"Push\")\n",
    "                target.pop(0)\n",
    "                continue\n",
    "            if target and  x < target[0]  :\n",
    "                ans.append(\"Push\")\n",
    "                ans.append(\"Pop\")\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        i = 1\n",
    "        ans = []\n",
    "        for x in target:\n",
    "            if x != i:\n",
    "                for _ in range(x - i):\n",
    "                    ans.append(\"Push\")\n",
    "                    ans.append(\"Pop\")\n",
    "            i = x + 1\n",
    "            ans.append(\"Push\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        l1 = []\n",
    "        p = 1\n",
    "        for i in range (len(target)):\n",
    "            if target[i] == p:\n",
    "                l1.append(\"Push\")\n",
    "                p += 1\n",
    "            else:\n",
    "                while target[i] != p:\n",
    "                    l1.append(\"Push\")\n",
    "                    l1.append(\"Pop\")\n",
    "                    p += 1\n",
    "                l1.append(\"Push\")\n",
    "                p += 1\n",
    "        return l1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        prv = 0\n",
    "        res = []\n",
    "        for t in target:\n",
    "            res.extend([\"Push\", \"Pop\"]*(t-prv-1)+[\"Push\"])\n",
    "            prv = t\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans = []\n",
    "        for i in range(1,n+1):\n",
    "            \n",
    "            if i in target:\n",
    "                ans.append('Push')\n",
    "            else:\n",
    "                ans.append('Push')\n",
    "                ans.append('Pop')\n",
    "            if i == target[-1]:\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        i=0\n",
    "        j=1\n",
    "        while j <= n:\n",
    "            if i<len(target) and j == target[i]:\n",
    "                res.append('Push')\n",
    "                i+=1\n",
    "            elif i<len(target) and j != target[i]:\n",
    "                res.extend(['Push','Pop'])\n",
    "            j+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        t_index = 0\n",
    "        n = len(target)\n",
    "        stk = []\n",
    "        num = 1\n",
    "        res = []\n",
    "        while t_index < n:\n",
    "            if num == target[t_index]:\n",
    "                if t_index == 0:\n",
    "                    while stk:\n",
    "                        stk.pop()\n",
    "                        res.append(\"Pop\")\n",
    "                    stk.append(num)\n",
    "                    res.append(\"Push\")\n",
    "                    t_index += 1\n",
    "                    num+=1\n",
    "                else:\n",
    "                    while (top:=stk[-1]) != target[t_index-1]:\n",
    "                        res.append(\"Pop\")\n",
    "                        stk.pop()\n",
    "                    stk.append(num)\n",
    "                    res.append(\"Push\")\n",
    "                    t_index += 1\n",
    "                    num += 1\n",
    "            else:\n",
    "                stk.append(num)\n",
    "                res.append(\"Push\")\n",
    "                num += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        lst = list(range(1, n+1))\n",
    "        a = 0\n",
    "        b = 0\n",
    "        push = 'Push'\n",
    "        pop = 'Pop'\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if a == len(target) :\n",
    "                    return ans\n",
    "            if target[a] == lst[i]:\n",
    "                ans.append(push)\n",
    "                a += 1\n",
    "            else:\n",
    "                ans.append(push)\n",
    "                ans.append(pop)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ret = []\n",
    "        for x in range(1, target[-1]+1):\n",
    "            ret.append('Push')\n",
    "            if x not in target:\n",
    "                ret.append('Pop')\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "#       result=[]\n",
    "#       j=0\n",
    "\n",
    "#       for i in range(1,n+1):\n",
    "\n",
    "#         result.append('Push')\n",
    "\n",
    "#         if target[j]==i:\n",
    "#           j+=1\n",
    "#         else:\n",
    "#           result.append('Pop')\n",
    "        \n",
    "#         if j==len(target):\n",
    "#           break          \n",
    "#       return result\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "      pointer=0\n",
    "      result=[]\n",
    "\n",
    "      for i in range(1,n+1):\n",
    "        if target[pointer]==i:\n",
    "          result.append('Push')\n",
    "          pointer+=1\n",
    "        elif target[pointer]>i:\n",
    "          result.append('Push')\n",
    "          result.append('Pop')\n",
    "        if pointer>=len(target):\n",
    "          return result\n",
    "      return result     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ret = []\n",
    "        for _ in range(target[0]-1):\n",
    "            ret += ['Push', 'Pop']\n",
    "        ret.append('Push')\n",
    "        for i in range(len(target)-1):\n",
    "            for _ in range(target[i+1]-target[i]-1):\n",
    "                ret += ['Push', 'Pop']\n",
    "            ret.append('Push')\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        n = 1\n",
    "        r = []\n",
    "        for i in target:\n",
    "            while i != n:\n",
    "                r.append('Push')\n",
    "                r.append('Pop')\n",
    "                n += 1\n",
    "            r.append('Push')\n",
    "            n += 1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res=[]\n",
    "        a=0\n",
    "        for i in target:\n",
    "            for _ in range(i-a-1):\n",
    "                res.append('Push')\n",
    "                res.append('Pop')\n",
    "            res.append('Push')\n",
    "            a=i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(1, target[-1]+1):\n",
    "            res.append(\"Push\")\n",
    "            if i not in target:\n",
    "                res.append(\"Pop\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res=[]\n",
    "        prev=0\n",
    "        for num in target:\n",
    "            for i in range(num-prev-1):\n",
    "                res.append('Push')\n",
    "                res.append('Pop')\n",
    "            res.append('Push')\n",
    "            prev=num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        cur = 0\n",
    "        ans = []\n",
    "        for v in target:\n",
    "            cur += 1\n",
    "            while cur < v:\n",
    "                ans.extend(['Push','Pop'])\n",
    "                cur += 1\n",
    "            ans.append('Push')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans=[]\n",
    "        i=0\n",
    "        count=0\n",
    "        while i<len(target):\n",
    "            if target[i]==count+1:\n",
    "                ans.append('Push')\n",
    "                i+=1\n",
    "                count+=1\n",
    "            else:\n",
    "                ans.append('Push')\n",
    "                ans.append('Pop')\n",
    "                count+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        list1=[]\n",
    "        list2=[]\n",
    "        j=0\n",
    "        for i in range(1,n+1):\n",
    "            if i==target[j]:\n",
    "                list1.append(\"Push\")\n",
    "                list2.append(i)\n",
    "                j+=1\n",
    "            else:\n",
    "                list1.append(\"Push\")\n",
    "                list1.append(\"Pop\")\n",
    "            if list2==target:\n",
    "                return list1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        res = []\n",
    "        idx = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if idx == len(target):\n",
    "                break\n",
    "            res.append(\"Push\")\n",
    "            if target[idx] != i:\n",
    "                res.append(\"Pop\")\n",
    "            else:\n",
    "                idx += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def buildArray(self, target: List[int], n: int) -> List[str]:\n",
    "        ans = []  # 用于存储操作序列\n",
    "        j = 0     # 用于追踪目标数组的当前元素\n",
    "\n",
    "        for i in range(1, n + 1):  # 从 1 遍历到 n\n",
    "            if j >= len(target):\n",
    "                break  # 如果目标数组已构建完成，停止遍历\n",
    "\n",
    "            ans.append(\"Push\")  # 先执行 \"Push\" 操作\n",
    "            if target[j] == i:\n",
    "                j += 1  # 如果该元素在目标数组中，移动到目标数组的下一个元素\n",
    "            else:\n",
    "                ans.append(\"Pop\")  # 如果该元素不在目标数组中，执行 \"Pop\" 操作\n",
    "\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
